package com.leetcode.贪心;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * @author LZF
 *
 */
public class L56合并区间 {
	public static void main(String[] args) {
		
	}
	/**
	 * 对区间进行排序，按开始坐标排序，从前往后遍历，也可以按结束坐标排序，但是需要从后往前遍历
	 * 这里是从前往后遍历
	 * 
	 * 合并区间是思路见 L452用最少数量的箭引爆气球 ，思路是一样，但是那道题是取区间的重叠
	 * 只是匹配规则不一样而已。
	 * @param intervals
	 * @return
	 */
	public static int[][] merge(int[][] intervals) {
		//按开始坐标排序
		Arrays.sort(intervals,(o1,o2) -> Integer.compare(o1[0],o2[0]));
		List<int[]> result = new ArrayList<>();
		for(int i = 1;i < intervals.length;i++) {
			if(intervals[i][0] <= intervals[i - 1][1]) {
				//可以合并
				intervals[i][0] = intervals[i - 1][0];//开始坐标取最小的，因为已经排序了，所以i - 1比i的小
				intervals[i][1] = Math.max(intervals[i][1],intervals[i - 1][1]);//结束坐标取最大
			} else {
				result.add(intervals[i - 1]);
			}
		}
		result.add(intervals[intervals.length - 1]);
		int[][] endResult = new int[result.size()][];
		return result.toArray(endResult);
    }
}
